In the current age of information technology, massive volumes of data are generated, stored and processed, to meet innumerable needs. Over the years, much effort has been devoted to developing better data storage and sort technologies, in order to handle the data expansion that has occurred, both in volume and use of data.
One aspect of efforts to manage the ever-expanding volume of and reliance on data involves the evolution of database technology and, specifically, relational database technology. In relational databases, rows are composed of multiple columns. During processing of data from a database, the data items extracted from rows are frequently ordered by one or more associated columns or fields. The fields by which data items are sorted are referred to as sort keys. For example, a query on a table may be as follows:                select * from emp order by surname, first_name, social_security_no. In this example, the surname, first_name, and social_security_no fields are all sort keys.Sort Algorithms        
Sort algorithms are used to sort data. Most sort algorithms are either comparison-based or radix-based. Popular comparison-based sort algorithms include quicksort, mergesort and heapsort. Popular radix-based sort algorithms include radix sort and bucket sort. Performance of a sort algorithm is measured by the number of times that work is performed for all of the data items being sorted.
—Comparison-Based Sort Algorithms
The performance of comparison-based sort algorithms is described by the number of comparisons that are required to order n items. The quicksort algorithm, a comparison-based algorithm, is described by C. A. R. Hoare, in “Partition: Algorithm 63,” “Quicksort: Algorithm 64,” and “Find: Algorithm 65.” Comm. ACM 4, 321-322, 1961. Generally, a quicksort algorithm uses the divide and conquer paradigm to sort items, in which (a) an item from the group of items being sorted is selected as the “pivot”, (b) the remaining items are partitioned (i.e., grouped) into two groups, those greater than (or greater than or equal to) the pivot and those less than the pivot, and (c) the groups are recursively sorted. Quicksort algorithms require O(n log n) comparisons to sort n items on average, and O(n2) comparisons in the worst case.
A quicksort algorithm generally has the following properties: (a) the algorithm can be implemented by a recursive function; (b) the number of keys to be examined by a recursive invocation decreases as the depth of recursion increases, (c) the keys to be examined by a recursive invocation are a subset of the keys examined by any ancestor on the call stack; and (d) all comparisons performed for a given invocation are performed before the recursive invocations are made.
—Radix-Based Sort Algorithms
The performance of radix-based sort algorithms is described by the number of times that each item must be examined. The radix sort algorithm, a multiple pass distribution sort algorithm, (a) distributes each item to a bucket according to part of the item's sort key beginning with the least significant part of the key (in the case of least significant digit (“LSD”) radix sort) or the most significant part of the key (in the case of most significant digit (“MSD”) radix sort), and after each pass, (b) collects the items from the buckets, in relative order, to redistribute based on the next most significant (for LSD radix sort), or the next least significant (for MSD radix sort) part of the key. Radix sort algorithms require n* key_size comparisons to sort n items on average, where “key_size” is the size of the sort key.
Hence, when “key_size” is less than log(n), radix-based sort algorithms are faster than comparison-based sort algorithms. That is, generally, when “key size” is small, radix sort algorithms are faster than comparison-based sort algorithms, and when “key_size” is large, comparison-based sort algorithms are faster than radix-based sort algorithms.